package 回溯;

import com.google.common.collect.Lists;

import java.util.*;

/**
 * todo
 *
 * @author songZiHao
 * @version 1.0.0
 * @ClassName 单词拆分139.java
 * @createTime 2024年03月07日 17:47:00
 */
public class 单词拆分139 {

	static Boolean result = false;
	static Map<Integer, Set<String>> listMap = new HashMap<>();
	static Set<Integer> dictType = new HashSet<>();
	static int max=0;
	public static boolean wordBreak(String s, List<String> wordDict) {
		for (String word : wordDict) {
			int length = word.length();
			Set<String> existStr = listMap.getOrDefault(length, new HashSet<>());
			existStr.add(word);
			listMap.put(length, existStr);
			dictType.add(length);
			max=Math.max(max,length);
		}
		backTrace(s,0);
		return result;
	}

	public static void backTrace(String s, int curIndex) {

		if (result) {
			return;
		}
		if (s.length() == curIndex) {
			result = true;
			return;
		}

		for (int i = curIndex; i < s.length(); i++) {
			String substring = s.substring(curIndex, i + 1);
			int length = (i - curIndex) + 1;
			if (dictType.contains(length)) {
				Set<String> existStr = listMap.get(length);
				if (existStr.contains(substring)) {
					backTrace(s, i + 1);
				}
			}
		}
	}

	public static void main(String[] args) {
		wordBreak("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab",
				Lists.newArrayList("a","aa","aaa","aaaa","aaaaa","aaaaaa","aaaaaaa","aaaaaaaa","aaaaaaaaa","aaaaaaaaaa"));
	}
}
